class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        x = len(matrix)
        if x == 0:
            return False
        y = len(matrix[0])
        if y == 0:
            return False
        xStart = 0
        yStart = 0
        while True:
            for i in range(x):
                if target == matrix[i][yStart]:
                    return True
                if target < matrix[i][yStart]:
                    x = i
                    break
            yStart = yStart + 1
            for i in range(y):
                if target == matrix[xStart][i]:
                    return True
                if target <= matrix[xStart][i]:
                    y = i
                    break
            xStart = xStart + 1
            if xStart < x and yStart < y:
                continue
            else:
                return False


if __name__ == '__main__':
    so = Solution()
    s = [
        [1, 4, 7, 11, 15],
        [2, 5, 8, 12, 19],
        [3, 6, 9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30]
    ]
    target = 19
    r = so.searchMatrix(s, target)
    print(r)
